DSC 40B Practice Problems

Problems tagged with "asymptotic notation"

Problem #013

Tags: asymptotic notation

Let \(f(n) = \displaystyle\frac{n^3 - 2n^2 + 100}{n + 10}\) True or False: \(f(n) = O(n^4)\)

True False
Solution

True.

Problem #014

Tags: asymptotic notation

Suppose \(f(n) = \Omega(n^3)\) and \(g(n) = \Omega(n)\).

True or False: it is necessarily the case that \(f/g = \Omega(n^2)\).

True False
Solution

False.

Problem #015

Tags: asymptotic notation

Let \(f(n) = n \cdot(\sin{n} + 1 )\). A plot of this function is shown below.

True or False: \(f(n) = \Theta(n)\).

True False
Solution

False.

Remember that for \(f(n)\) to be \(\Theta(n)\), it has to be both upper- and lower-bounded by some positive constant times \(n\). This function is upper bounded by \(O(n)\), but it doesn't have a lower bound of \(\Omega(n)\). Therefore, it can't be \(\Theta(n)\).

In other words, there is no positive constant \(c\) and no positive number \(N\) such that \(f(n) > c n\) for all \(n > N\).

If you had to describe this function in asymptotic notation, you could say that \(f(n) = O(n)\)(and that would be a tight upper bound), but there is no lower bound, since the function keeps coming back down to zero.

Problem #025

Tags: asymptotic notation

Let \(f\) be the piecewise function defined as:

\[ f(n) = \begin{cases} 1, & \text{if $n$ is a multiple of 1 million},\\ n^2, &\text{otherwise}. \end{cases}\]

If you were to plot \(f\), the function would look like \(n^2\), but would have point discontinuities where it ``jumps'' back to 1 whenever \(n\) is a multiple of 1 million.

True or False: \(f(n) = \Theta(n^2)\).

True False
Solution

False.

\(f(n)\)is upper bounded by \(O(n^2)\), but it doesn't have a lower bound of \(\Omega(n^2)\), which is necessary for it to be \(\Theta(n^2)\).

To see why, remember that for \(f(n)\) to be \(\Omega(n^2)\), there must be a positive constant \(c\) so that \(f(n)\) stays above \(c\cdot n^2\) for all \(n\) greater than some \(n_0\), meaning that it goes above \(c n^2\)and it stays above $c n^2$ forever, after some point.

Pick whatever positive \(c\) you'd like -- the function \(c\cdot n^2\) grows larger and larger as \(n\) increases, and eventually becomes larger than 1. But the function \(f(n)\) keeps dipping down to 1, meaning that it doesn't stay above \(c\cdot n^2\) for all \(n\) when \(n\) is large. Therefore, \(f(n)\) is not \(\Omega(n^2)\), and therefore also not \(\Theta(n^2)\).

Problem #026

Tags: asymptotic notation

Suppose \(f(n)\) is both \(O(n^2)\) and \(\Omega(n)\), and suppose \(g(n) = \Theta(n^3)\). What are the tightest possible asymptotic bounds that can be placed on \(f + g\)?

If the upper and lower bounds are the same, you may use \(\Theta\). If the upper and lower bounds are different, you should state them separately using \(O\) and \(\Omega\).

Solution

\(\Theta(n^3)\)

Problem #029

Tags: asymptotic notation

Consider the function \(f(n) = \frac{n^8 + 2^{3 + \log n} - \sqrt n}{20 n^5 - n^2}\).

True or False: \(f(n) = O(n^{4})\).

True False
Solution

True.

Problem #031

Tags: asymptotic notation

Suppose \(f_1(n) = O(g_1(n))\) and \(f_2(n) = \Omega(g_2(n))\). True or False: it is necessarily the case that \(f_1 + f_2 = O(g_1(n))\).

True False
Solution

False.

Problem #033

Tags: asymptotic notation

Let \(f\) and \(g\) be as in the previous question. What are the tightest possible asymptotic bounds that can be placed on the product, \(f \times g\)?

As before, if the upper and lower bounds are the same, you may use \(\Theta\); otherwise you should use \(O\) and \(\Omega\).

Solution

\(O(n^5)\) and \(\Omega(n^4)\)

Problem #043

Tags: asymptotic notation

Consider the function \(f(n) = \frac{n^8 + 2^{3 + \log n} - \sqrt n}{20 n^5 - n^2}\).

True or False: \(f(n) = \Omega(n^2)\).

True False
Solution

True.

Problem #045

Tags: asymptotic notation

Suppose Algorithm A takes \(\Theta(n^2)\) time, while Algorithm B takes \(\Theta(2^n)\) time. True or False: there could exist an input on which Algorithm \(B\) takes less time than Algorithm A.

True False
Solution

True.

Problem #046

Tags: asymptotic notation

Let

\[ f(n) = \frac{n^3 - 2n + 100}{\sqrt n}\cdot\frac{n}{n^3 + n^2 + \sin n}\cdot n^2 \]

True or False: \(f(n) = \Theta(n^2)\).

True False
Solution

False.

Problem #054

Tags: asymptotic notation

Consider the function \(f(n) = n \times(\sin(n) + 1)\). A plot of this function is shown below:

True or False: this function is \(O(1 + \sin n)\).

True False
Solution

False.

\(f(n)\) grows arbitrarily large, while \(\sin n + 1\) is bounded above by 2.

More formally, there is no constant \(c\) such that \(c (1 + \sin n)\) upper bounds \(f(n)\) for all large \(n\).

Problem #057

Tags: asymptotic notation

Suppose \(f_1(n)\) is \(O(n^2)\) and \(\Omega(n)\). Also suppose that \(f_2(n) = \Theta(n^2)\).

Consider the function \(g(n) = f_2(n) / f_1(n)\). True or false: it must be the case that \(g(n) = \Omega(n)\).

True False
Solution

False.

Problem #058

Tags: asymptotic notation

Suppose \(f_1(n) = \Omega(g_1(n))\) and \(f_2 = \Omega(g_2(n))\). Define \(f(n) = \min\{ f_1(n), f_2(n) \}\) and \(g(n) = \min\{ g_1(n), g_2(n)\}\).

True or false: it is necessarily the case that \(f(n) = \Omega(g(n))\).

True False
Solution

True.

Problem #060

Tags: asymptotic notation

Consider again the function \(f(n) = n \times( \sin(n) + 1)\) from the previous problem.

True or False: \(f(n) = O(n^3)\).

True False
Solution

True.

Problem #070

Tags: asymptotic notation

Suppose \(f_1(n)\) is \(O(n^2)\) and \(\Omega(n)\). Also suppose that \(f_2(n) = \Theta(n^2)\).

Consider the function \(f(n) = f_1(n) + f_2(n)\). True or false: it must be the case that \(f(n) = \Theta(n^2)\).

True False
Solution

True.

Problem #073

Tags: asymptotic notation

Let

\[ f(n) = 5 n \log n + \frac{n^3 + 5}{n + 2 + |\sin \pi n|} + n \sqrt n \]

Write \(f\) in asymptotic notation in as simplest terms possible.

Solution

\(f(n) = \Theta(n^2)\)

Problem #091

Tags: asymptotic notation

Suppose \(f_1(n) = O(g_1(n))\) and \(f_2 = O(g_2(n))\). Define \(f(n) = \min\{ f_1(n), f_2(n) \}\) and \(g(n) = \min\{ g_1(n), g_2(n) \}\). True or false, it is necessarily the case that \(f(n) = O(g(n))\).

True False
Solution

True.

Problem #093

Tags: asymptotic notation

Suppose \(f(n) = \Omega(n^3)\) and \(g(n) = \Omega(n)\).

True or False: it is necessarily the case that \(f/g = \Omega(n^2)\).

True False
Solution

False.